Solving Nonograms by combining relaxations.
Nonograms, also known as Japanese puzzles, are a specific type of logic drawing puzzles. The challenge is to fill a grid with black and white pixels in such a way that a given description for each row and column, indicating the lengths of consecutive segments of black pixels, is adhered to. Although the Nonograms in puzzle books can usually be solved by hand, the general problem of solving Nonograms is NP-hard. In this paper, we propose a reasoning framework that can be used to determine the value of certain pixels in the puzzle, given a partial filling. Constraints obtained from relaxations of the Nonogram problem are combined into a 2-SAT problem, which is used to deduce pixel values in the Nonogram solution. By iterating this procedure, starting from an empty grid, it is often possible to solve the puzzle completely. All the computations involved in the solution process can be performed in polynomial time. Our experimental results demonstrate that the approach is capable of solving a variety of Nonograms that cannot be solved by simple logic reasoning within individual rows and columns, without resorting to branching operations. In addition, we present statistical results on the solvability of Nonograms, obtained by applying our method to a large number of Nonograms.
Temporal Extrapolation within a Static Clustering.
Predicting the behaviour of individuals is a core business of policy makers. This paper discusses a new way of predicting the “movement in time ” of items through pre-defined classes by analysing their changing placement within a static, preconstructed 2-dimensional clustering. It employs the visualization realized in previous steps within item analysis, rather than performing complex calculations on each attribute of each
A Reasoning Framework for Solving Nonograms.
Nonograms, also known as Japanese puzzles, are a specific type of logic drawing puzzles. The challenge is to fill a grid with black and white pixels in such a way that a given description for each row and column, indicating the lengths of consecutive segments of black pixels, is adhered to. Although the Nonograms in puzzle books can usually be solved by hand, the general problem of solving Nonograms is NP-hard. In this paper, we propose a reasoning framework that can be used to determine the value of certain pixels in the puzzle, given a partial filling. Constraints obtained from relaxations of the Nonogram problem are combined into a 2-SAT problem, which is used to deduce pixel values in the Nonogram solution. By iterating this procedure, starting from an empty grid, it is often possible to solve the puzzle completely. All the computations involved in the solution process can be performed in polynomial time. Our experimental results demonstrate that the approach is capable of solving a variety of Nonograms that cannot be solved by simple logic reasoning within individual rows and columns, without resorting to branching operations. In addition, we present statistical results on the solvability of Nonograms, obtained by applying our method to a large number of Nonograms.
An Early Warning System for the Prediction of Criminal Careers.

Selection of DNA Markers.
Abstract — Given a genome, i.e., a long string over a fixed finite alphabet, the problem is to find short (dis)similar substrings. This computationally intensive task has many biological applications. We first describe an algorithm to detect substrings that have edit distance to a fixed substring at most equal to a given e. We then propose an algorithm that finds the set of all substrings that have edit distance larger than e to all others. Several applications are given, where attention is paid to practical biological issues such as hairpins and GC percentage. An experiment shows the potential of the methods. I.
On Affect and Self%2Dadaptation Potential Benefits of Valence%2DControlled Action%2DSelection.
Abstract. Psychological studies have shown that emotion and affect influence learning. We employ these findings in a machine-learning metaparameter context, and dynamically couple an adaptive agent’s artificial affect to its action-selection mechanism (Boltzmann β). The agent’s performance on two important learning problems is measured. The first consists of learning to cope with two alternating goals. The second consists of learning to prefer a later larger reward (global optimum) for an earlier smaller one (local optimum). Results show that, compared to several control conditions, coupling positive affect to exploitation and negative affect to exploration has several important benefits. In the alternatinggoal task, it significantly reduces the agent’s goal-switch search peak. The agent finds its new goal faster. In the second task, artificial affect facilitates convergence to a global instead of a local optimum, while permitting to exploit that local optimum. We conclude that affect-controlled action-selection has adaptation benefits. 1
Visualization and Grouping of Graph Patterns in Molecular Databases.
Mining subgraphs is an area of research where we have a given set of graphs, and we search for (connected) subgraphs contained in these graphs. In this paper we focus on the analysis of graph patterns where the graphs are molecules and the subgraphs are patterns. In the analysis of fragments one is interested in the molecules in which the patterns occur. This data can be very extensive and in this paper we introduce a technique of making it better available using visualization. The user does not have to browse all the occurrences in search of patterns occurring in the same molecules; instead the user can directly see which subgraphs are of interest. 1
Metrics for Mining Multisets.
Abstract. We propose a new class of distance measures (metrics) designed for multisets, both of which are a recurrent theme in many data mining applications. One particular instance of this class originated from the necessity for a clustering of criminal behaviours. These distance measures are parameterized by a function f which, given a few simple restrictions, will always produce a valid metric. This flexibility allows these measures to be tailored for many domain-specific applications. In this paper, the metrics are applied in bio-informatics (genomics), criminal behaviour clustering and text mining. The metric we propose also is a generalization of some known measures, e.g., the Jaccard distance and the Canberra distance. We discuss several options, and compare the behaviour of different instances. 1
An efficient
Boolean Satisfiability is probably the most studied of combinatorial optimization/search problems. Significant effort has been devoted to trying to provide practical solutions to this problem for problem instances encountered in a range of applications in Electronic Design Automation (EDA), as well as in Artificial Intelligence (AI). This study has culminated in the development of several SAT packages, both proprietary and in the public domain (e.g. GRASP, SATO) which find significant use in both research and industry. Most existing complete solvers are variants of the Davis-Putnam (DP) search algorithm. In this paper we describe the development of a new complete solver, Chaff, which achieves significant performance gains through careful engineering of all aspects of the search -- especially a particularly efficient implementation of Boolean constraint propagation (BCP) and a novel low overhead decision strategy. Chaff has been able to obtain one to two orders of magnitude performance improvement on difficult SAT benchmarks in comparison with other solvers (DP or otherwise), including GRASP and SATO.
Clustering Co%2Doccurrence of Maximal Frequent Patterns in Streams

Clustering with Lattices in the Analysis of Graph Patterns

Mining Patterns with a Balanced Interval

Data Mining Approaches to Criminal Career Analysis.
Abstract — Narrative reports and criminal records are stored digitally across individual police departments, enabling the collection of this data to compile a nation-wide database of criminals and the crimes they committed. The compilation of this data through the last years presents new possibilities of analyzing criminal activity through time. Augmenting the traditional, more socially oriented, approach of behavioral study of these criminals and traditional statistics, data mining methods like clustering and prediction enable police forces to get a clearer picture of criminal careers. This allows officers to recognize crucial spots in changing criminal behaviour and deploy resources to prevent these careers from unfolding. Four important factors play a role in the analysis of criminal careers: crime nature, frequency, duration and severity. We describe a tool that extracts these from the database and creates digital profiles for all offenders. It compares all individuals on these profiles by a new distance measure and clusters them accordingly. This method yields a visual clustering of these criminal careers and enables the identification of classes of criminals. The proposed method allows for several user-defined parameters. I.
A Neural Network Approach to Real%2DTime Discrete Tomography.

A Distance Measure for Determining Similarity Between Criminal Investigations.
Abstract. The information explosion has led to problems and possibilities in many areas of society, including that of law enforcement. In comparing individual criminal investigations on similarity, we seize one of the opportunities of the information surplus to determine what crimes may or may not have been committed by the same group of individuals. For this purpose we introduce a new distance measure that is specifically suited to the comparison between investigations that differ largely in terms of available intelligence. It employs an adaptation of the probability density function of the normal distribution to constitute this distance between all possible couples of investigations. We embed this distance measure in a four-step paradigm that extracts entities from a collection of documents and use it to transform a high dimensional vector table into input for a police operable tool. The eventual report is a two-dimensional representation of the distances between the various investigations and will assist the police force on the job to get a clearer picture of the current situation. 1
Consecutive Support Better Be Close%21

Neural Networks for Discrete Tomography.
Discrete tomography deals with the reconstruction of binary images from their projections in a small number of directions. In this paper we consider possible neural network approaches to this tomographic reconstruction problem. In particular we are interested in methods that can compute reconstructions in real-time and make efficient use of prior knowledge about the images, even when this knowledge is difficult to model by hand. We propose both a feedforward back-propagation network method and a Hopfield network method for solving the reconstruction problem. 1
Efficient Feature Detection for Sequence Classification in a Receptor Database.

Frequent Itemsets for Genomic Profiling.
Abstract. Frequent itemset mining is a promising approach to the study of genomic profiling data. Here a dataset consists of real numbers describing the relative level in which a clone occurs in human DNA for given patient samples. One can then mine, for example, for sets of samples that share some common behavior on the clones, i.e., gains or losses. Frequent itemsets show promising biological expressiveness, can be computed efficiently, and are very flexible. Their visualization provides the biologist with useful information for the discovery of patterns. Also it turns out that the use of (larger) frequent itemsets tends to filter out noise. 1
Detecting and Pruning Introns for Faster Decision Tree Evolution.

Genetic Programming for data classification partitioning the search space.
When Genetic Programming is used to evolve decision trees for data classification, search spaces tend to become extremely large. We present several methods using techniques from the field of machine learning to refine and thereby reduce the search space sizes for decision tree evolvers. We will show that these refinement methods improve the classification performance of our algorithms.
Tetris and decidability.

Tetris is hard%2C even to approximate.
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces  and must pack them into a rectangular gameboard initially occupied by a given configuration of  filled squares; any completely filled row of the gameboard is cleared and all pieces above it drop  by one row. We prove that in the o#ine version of Tetris, it is NP-complete to maximize the  number of cleared rows, maximize the number of tetrises (quadruples of rows simultaneously  filled and cleared), minimize the maximum height of an occupied square, or maximize the number  of pieces placed before the game ends. We furthermore show the extreme inapproximability of  the first and last of these objectives to within a factor of p    , when given a sequence of p  pieces, and the inapproximability of the third objective to within a factor of 2-#, for any # &gt; 0.
How to Construct Tetris Configurations.

Nonmetric multidimensional scaling Neural networks versus traditional techniques.

Apriori%2C A Depth First Implementation.
We will discuss ##, the depth first implementation of APRIORI as devised in 1999 (see [8]). Given a database, this algorithm builds a trie in memory that contains all frequent itemsets, i.e., all sets that are contained in at least minsup transactions from the original database. Here minsup  is a threshold value given in advance. In the trie, that is constructed by adding one item at a time, every path corresponds to a unique frequent itemset. We describe the algorithm in detail, derive theoretical formulas, and provide experiments.
Complexity Analysis of Depth First and FP%2DGrowth Implementations of APRIORI.

Nonmetric Multidimensional Scaling with Neural Networks.
In this paper we present a neural network for nonmetric multidimensional scaling. In our approach, the monotone transformation that is a part of every nonmetric scaling algorithm is performed by a special feedforward neural network with a modified backpropagation algorithm. Contrary to traditional methods, we thus explicitly model the monotone transformation by a special purpose neural network. The architecture of the new network and the derivation of the learning rule are given, as well as some experimental results. The experimental results are positive.
Interesting Fuzzy Association Rules in Quantitative Databases.
In this paper we examine association rules and their interestingness. Usually these rules are discussed in the world of basket analysis. Instead of customer data we now study the situation with data records of a more general but fixed nature, incorporating quantitative (nonboolean) data. We propose a method for finding interesting rules with the help of fuzzy techniques and taxonomies for the items/attributes. Experiments show that the use of the proposed interestingness measure substantially decreases the number of rules.
Theory of Genetic Algorithms.
this paper we introduce some methods for examining the fundamental properties of genetic algorithms ([Hol75, Jon75, Gol89, Mit96]), probabilistic search and optimization algorithms that work on populations of bit strings, i.e., strings of a fixed length consisting of zeroes and ones. Genetic algorithms are a subfield of evolutionary computation. For a good overview of evolutionary computation one may consult the Handbook of Evolutionary Computation [BFM97]. In the Handbook also many applications of genetic algorithms can be found. We do not give a complete overview of the theory of genetic algorithms; in future papers we intend to cover more related topics. We will present results and methods that give an impression of the kind of theory that is present in evolutionary computation today. We hope that this paper provides a starting point for researchers in theoretical computer science who are interested in the theory of evolutionary computation. This paper is an extended abstract of a paper that appeared in the Bulletin of the European Association for Theoretical Computer Science, Number 63, October 1997, pp. 161--192. 2 Evolutionary Computation
Natural Data Mining Techniques.
 In data selection the data most relevant to the problem at hand is selected, leaving out redundant data. In the cleaning process, the obvious aws in the data are corrected. In the coding process, data is coded such that it can be used in data mining algorithms. In the data mining process, the actual inference takes place. In the reporting process the results are of course reported, usually in a visually attractive way. KDD is closely connected to an other important development which is called data warehousing. A data warehouse is a central storage facility in which operational data is stored. These warehouses usually contain enormous amounts of data. This gives a new view on information management. The combination of KDD and data warehousing 1  allows companies to use the knowledge hidden in the data as a production factor, instead of just support for their operations. A usual problem in the eld of data mining is that the combination of databases (often called \data fusion&#034;) 
A Bayesian approach to combined neural networks forecasting.
. Suitable neural networks may act as experts for time series  predictions. The naive prediction is in a Bayesian manner used as prior  to steer the weighted combination of these experts.  The paper was presented at ESANN&#039;2000, The 8th European Symposium  on Articial Neural Networks, in Brugge (Belgium), April 26-28, 2000.  1. Introduction  Predicting the near future using information from the past is a challenging task. In this paper we try to do so by combining neural networks and techniques from Bayesian statistics (cf. [1] and [6]) in order to generate a prediction for an observable y t+1 , given the time series y 1 ; y 2 ; : : : ; y t .  We start from the following observations. First it is hard to beat naive predictions|y t in the setting above. Secondly, it is a complicated matter to combine expert forecasts into better ones. We feel that a joined eort might generate better results, especially if neural networks support the process. For this purpose we use so-called FIR networ...
Natural Data Mining Techniques.
 In data selection the data most relevant to the problem at hand is selected, leaving out redundant data. In the cleaning process, the obvious aws in the data are corrected. In the coding process, data is coded such that it can be used in data mining algorithms. In the data mining process, the actual inference takes place. In the reporting process the results are of course reported, usually in a visually attractive way. KDD is closely connected to an other important development which is called data warehousing. A data warehouse is a central storage facility in which operational data is stored. These warehouses usually contain enormous amounts of data. This gives a new view on information management. The combination of KDD and data warehousing 1  allows companies to use the knowledge hidden in the data as a production factor, instead of just support for their operations. A usual problem in the eld of data mining is that the combination of databases (often called \data fusion&#034;) 
Mining Clusters with Association Rules.
In this paper we propose a method for extracting clusters in a population of customers, where the only information available is the list of products bought by the individual clients. We use association rules having high confidence to construct a hierarchical sequence of clusters. A specific metric is introduced for measuring the quality of the resulting clusterings. Practical consequences are discussed in view of some experiments on real life datasets.
Fourier Analysis of Genetic Algorithms.
We propose a general framework for Fourier analysis in the field of genetic algorithms. We introduce special functions, analogous to sine and cosine for real numbers, that have nice properties with respect to genetic operations such as mutation and crossover. The special functions we introduce are generalizations of bit products and Walsh products. As applications, we trace (both analytically and numerically) the behavior of genetic algorithms, and obtain results on the fitness of schemata. 1 Introduction  In this paper we introduce a method for examining the fundamental properties of genetic algorithms (see [8,12]). A genetic algorithm works on a multiset of bit strings of fixed length. A fitness function is given which measures the quality of the elements of the multiset. The elements of the multiset are usually called individuals and the multiset is called the population. A genetic algorithm applies genetic operators in order to improve the multiset. Standard genetic operators are p...
Maximum Likelihood Weights for a Linear Ensemble of Regression Neural Networks.
In this we paper study the problem of combining the outputs of the members of an ensemble of neural networks. We review the commonly used methods and thoroughly derive a cost function from a maximum likelihood perspective, that can be minimized in order to obtain maximum likelihood weights. The solution is shown to be closely related to a well known statistical method. The various combination methods are tested on several data-sets, with encouraging results.  KEYWORDS: ensembles, maximum likelihood, neural networks  1. Introduction  Recently, neural network researchers have devoted a lot of attention to neural network ensembles [4, 6, 5]. In neural network ensembles, the outputs of different neural networks trained for the same problem are used to form a combined prediction. This combination is usually linear. Much effort has been put into determining the `best&#039; coefficients of the linear combination, but the currently existing methods are more or less ad-hoc and lack a probabilistic b...
Two neural network methods for multidimensional scaling.
Multidimensional scaling (MDS) embeds points in a Euclidean space given only dissimilarity data. Only very recently MDS has gotten some attention from neural network researchers. We propose two neural network methods for MDS and evaluate them using both artificially generated and real data. Training uses two inputs at a time. 1 Introduction  Multidimensional scaling (MDS) is a well-known statistical technique that has been applied successfully to a variety of problems in the past. Generally stated, the classical MDS techniques attempt to find a coordinate representation for various objects between which only dissimilarities are given. Dissimilarities between objects are monotonically related to Euclidean distances between the objects. Various types of MDS procedures and objective functions have been presented in the past. Recently MDS also got some attention from neural network researchers [2, 3]. However, in [3] the focus is on MDS as a dimensionality reduction technique, and the prop...
Expected Heights in Heaps.

